package cn.initcap.algorithm.sort.n2;

import cn.initcap.algorithm.sort.SortTestHelper;
import cn.initcap.algorithm.sort.Student;

/**
 * O(n^2)排序算法
 * 算法实现过程：
 * 8 6 2 3 1 5 7 4
 * 每次找到最小的（进行位置替换）：
 * 1)1 6 2 3 8 5 7 4
 * 2)1 2 6 3 8 5 7 4
 * 3)1 2 3 6 8 5 7 4
 * 4)1 2 3 4 8 5 7 6
 * 5)1 2 3 4 5 8 7 6
 * 6)1 2 3 4 5 6 7 8
 * 7)1 2 3 4 5 6 7 8
 *
 * @author initcap
 * @date Created in 2018/6/20 PM4:37.
 */
public class SelectionSort {

    /**
     * 我们的算法类不允许产生任何实例
     */
    private SelectionSort() {
    }

    public static void sort(Comparable[] arr) {

        int n = arr.length;
        for (int i = 0; i < n; i++) {
            // 寻找[i, n)区间里的最小值的索引
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                // 使用compareTo方法比较两个Comparable对象的大小
                if (arr[j].compareTo(arr[minIndex]) < 0) {
                    minIndex = j;
                }
            }
            swap(arr, i, minIndex);
        }
    }

    private static void swap(Object[] arr, int i, int j) {
        Object t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    public static void main(String[] args) {

        // 测试排序算法辅助函数
        int N = 20000;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
        SortTestHelper.testSort("cn.initcap.algorithm.sort.n2.SelectionSort", arr);
        SortTestHelper.printArray(arr);

        // 测试Integer
        Integer[] a = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
        SelectionSort.sort(a);
        SortTestHelper.printArray(a);

        // 测试Double
        Double[] b = {4.4, 3.3, 2.2, 1.1};
        SelectionSort.sort(b);
        SortTestHelper.printArray(b);

        // 测试String
        String[] c = {"D", "C", "B", "A"};
        SelectionSort.sort(c);
        SortTestHelper.printArray(c);

        // 测试自定义的类 Student
        Student[] d = new Student[4];
        d[0] = new Student("D", 90);
        d[1] = new Student("C", 100);
        d[2] = new Student("B", 95);
        d[3] = new Student("A", 95);
        SelectionSort.sort(d);
        SortTestHelper.printArray(d);
    }

}
